package astudy.util;

import org.apache.commons.lang.StringUtils;


/**
 * reference: CLRS Chapter 6
 * @author wong.tong@gmail.com
 *
 */
public class MaxHeap<T extends Comparable> {
	
	private T[] _heap;
	private int _size;

	public MaxHeap(T[] ds) {

		this._heap = ds;
		this._size = this._heap.length;

		//initialize
		this._rebuild();
	}
	
	private void _rebuild() {
		
		for (int i = this._size/2; i > -1; i --) {
			this._max_heapify(i);
		}
	}
	
	public T popmax() {
		T max = this._heap[0];
		this._heap[0] = this._heap[this._size-1];
		this._heap[this._size-1] = max;
		
		this._size --;
		this._rebuild();
		return max;
	}
	
	private int _left(int i) {
		return (i<<1)+1;
	}
	
	private int _right(int i) {
		return (i<<1)+2;
	}
	
	@SuppressWarnings("unchecked")
	private void _max_heapify(int i) {
		
		// get max
		int l = _left(i);
		int max = -1;
		if (l < this._size && this._heap[l].compareTo(this._heap[i]) > 0) {
			max = l;
		} else {
			max = i;
		}
		int r = _right(i);
		if (r < this._size && this._heap[r].compareTo(this._heap[max]) > 0) {
			max = r;
		}
		// recursion
		if (max != i) {
			T tmp = this._heap[i];
			this._heap[i] = this._heap[max];
			this._heap[max] = tmp;
			
			_max_heapify(max);
		}
	}
	
	@Override
	public String toString() {
		return StringUtils.join(this._heap, ", ");
	}
}
